/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lenovo
 * Date: 2022-09-12
 * Time: 17:39
 */
public class BinarySearchTree {
    //创建一个节点
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    TreeNode root;


    /**
     * 二叉树查找
     * @param key
     */
    //返回值为boolean类型
    public boolean serach(int key){
        //空树
        if(root == null){
            return false;
        }
        TreeNode cur = root;
        //非空树
        while (cur!= null){
            //key 小于根节点,就往root的左子树里寻找
            if(key < cur.val){
                cur = cur.left;
            }else if( key > cur.val){
                cur = cur.right;
            }else {//找到了
                return true;

            }
        }
        //在while循环里没有找到,直接返回false
        return false;

    }
    //返回值为TreeNode类型
    public TreeNode search(int key){
        //空树
        if(root == null){
            return null;
        }
        TreeNode cur = root;
        //非空树
        while (cur != null){
            //key>根节点,key在右子树里找
            if(key>cur.val){
                cur = cur.right;
                //key<根节点,key在左子树里找
            }else if(key < cur.val){
                cur = cur.left;
            }else {//找到了,返回cur
                return cur;
            }
        }
        //在while循环里没有找到,直接返回null
        return null;
    }
    /**
     * 二叉树插入
     * 二叉搜索树都是在叶子节点处插入
     */
    public boolean insert (int key){
        //将key值转化为节点
        TreeNode node = new TreeNode(key);
        TreeNode cur = root;
        TreeNode parent = null;
         //空树
        if(root == null){
            root = node;
            return true;
        }
        //非空树
        while (cur != null) {
            //key 小于根节点,往左边找
            if(cur.val > key){
                parent = cur;
                cur = cur.left;
                //key大于根节点,往右边找
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else{//key与根节点一样,不用插入
                return false;
            }

        }
        //代码走到这里,cur==null,parent里记录了cur的父亲节点,可以完成插入了
       //key 大于parent节点,key作为parent的右孩子
        if(key >parent.val){
            parent.right = node;
            return true;
        }else{//key 小于parent节点,key作为parent的左孩子
            parent.left = node;
            return true;
        }

    }
    /**
     * 二叉树的删除
     */
    public  void  delete(int key){
        //空树
        if(root == null){
            return;
        }
        //非空树
        //先找到key
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null){
            if(key  < cur.val){
                parent = cur;
                 cur = cur.left;
            }else if(key > cur.val){
                parent = cur;
                cur = cur.right;
            }else {//找到了,替换删除
                removeNode(cur,parent);
            }
        }
    }

    private void removeNode(TreeNode cur, TreeNode parent) {
        //1.cur没有左子树
        if(cur.left == null){
            //cur是根节点
            if(cur == root){
               root = root.right;
               //cur不是根节点,且cur= parent.left
            }else if(cur == parent.left){
                parent.left = cur.right;
            }else{
                parent.right = cur.right;
            }
        }
        //2.cur没有右子树
        if(cur.right == null){
            //cur是根节点
            if(cur == root){
                root = root.left;
                //cur不是根节点,且cur= parent.left
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
        }
        //3.有左右子树
        /**
         * target用来找替换值
         * targetParent用来记录target的父亲节点,要来删除
         */
        TreeNode targetParent = cur;
        //去cur的右子树里寻找最小值
        TreeNode target = cur.right;
        //在cur的右子树里找最大值
        while(target.left != null){
            targetParent = target;
            target = target.left;
        }
        //代码走到这里,target的左孩子为空,target里记录的是右子树里的最小值
        /**
         * 分两种情况:1.targetParent有左子树
         *          2.targeParent没有左子树
         */
        cur.val= target.val;
        if(targetParent.left == cur){
            targetParent.left = cur.right;
        }else{
            targetParent.right = cur.right;
        }
    }
    /**
     * 二叉树的中序遍历
     */
    public void inorder(TreeNode root){
        //空树
        if(root == null){
            return;
        }
        //左
        inorder(root.left);
        //根
        System.out.print(root.val + " ");
        //右
        inorder(root.right);
    }
}
